<hr>
<p>title: 338.Counting Bits<br>date: 2021-11-01 17:06:27<br>mathjax: true<br>tags:</p>
<pre><code>- LeeCode
</code></pre><p>categories: </p>
<pre><code>- LeeCode
</code></pre><p>hidden: true</p>
<h2 id="cateHidden-false"><a href="#cateHidden-false" class="headerlink" title="cateHidden: false"></a>cateHidden: false</h2><h3 id="描述"><a href="#描述" class="headerlink" title="描述"></a>描述</h3><blockquote>
<p>Given an integer n, return an array ans of length n + 1 such that for each i (0 &lt;= i &lt;= n), ans[i] is the number of 1’s in the binary representation of i.</p>
<p>给定一个整数 n，返回一个长度为 n + 1 的数组 ans，使得对于每个 i (0 &lt;= i &lt;= n)，ans[i] 是 i 的二进制表示中 1 的数量。</p>
</blockquote>
<h3 id="测试用例"><a href="#测试用例" class="headerlink" title="测试用例"></a>测试用例</h3><pre><code class="lang-bash">Input: n = 2 
Output: [0,1,1]
Explanation:
0 --&gt; 0 # 0个1
1 --&gt; 1 # 1个1
2 --&gt; 10 # 1个1

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --&gt; 0 # 0个1
1 --&gt; 1 # 1个1
2 --&gt; 10 # 1个1
3 --&gt; 11 # 2个1
4 --&gt; 100 # 1个1
5 --&gt; 101 # 2个1
</code></pre>
<h3 id="题解"><a href="#题解" class="headerlink" title="题解"></a>题解</h3><h4 id="amp-运算符（按位与）"><a href="#amp-运算符（按位与）" class="headerlink" title="&amp;运算符（按位与）"></a><code>&amp;</code>运算符（按位与）</h4><p>以特定的方式的方式组合操作数中对应的位 如果对应的位都为1，那么结果就是1， 如果任意一个位是0 则结果就是0。</p>
<pre><code class="lang-bash"># 1 &amp; 3的结果为1
1的二进制表示为 0 0 0 0 0 0 1
3的二进制表示为 0 0 0 0 0 1 1
根据 &amp; 的规则 得到的结果为 0 0 0 0 0 0 0 1，十进制表示就是1
</code></pre>
<h4 id="n-1"><a href="#n-1" class="headerlink" title="n - 1"></a><code>n - 1</code></h4><p>一个二进制的数减1，就是将这个二进制<strong>最右边的那个1</strong>变成0，然后它后边的所有位置都变成1（即将最右边的那个1和后面的所有数反转）。</p>
<p>举例：<code>0011 0100</code>，减1，(n-1)后变成：<code>0011 0011</code>。</p>
<p>所以<code>n &amp; (n - 1)</code>会将有0的位置都变成0，所以就是在原来的基础上去掉了一个1（<strong>最右边的那个1</strong>）。</p>
<p><code>0011 0100</code> &amp; <code>0011 0011</code> 即 <code>0011 0000</code>。</p>
<h4 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h4><pre><code class="lang-js">var countBits = function(n) {
    let count = 0, ans = [];
    for(let i = 0; i &lt;= n; i++) {
        let j = i;
        while(j) {
            count++;
            j &amp;= (j - 1);
        }
        ans.push(count);
        count = 0;
    }
    return ans
};
</code></pre>
<h3 id="结果"><a href="#结果" class="headerlink" title="结果"></a>结果</h3><blockquote>
<p>Accepted</p>
<p>15/15 cases passed (92 ms)</p>
<p>Your runtime beats 92.07 % of javascript submissions</p>
<p>Your memory usage beats 44.7 % of javascript submissions (45.2 MB)</p>
</blockquote>
